package LeetCode._02算法基础.day06广度深度优先搜索;

import org.junit.Test;
import 题组.Solution;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 16 - 10:51
 * @Description 有 n 个城市，其中一些彼此相连，另一些没有相连。
 * 如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
 * 而 isConnected[i][j] = 0 表示二者不直接相连。
 * 返回矩阵中 省份 的数量。
 * @Version 中等
 */
public class _547省份数量 {
    static int[][] isConnected = {
            {1,1,0},
            {1,1,0},
            {0,0,1}
    };
    @Test
    public void solve(){
        int res = findCircleNum(isConnected);
        System.out.println(res);
    }
    /*by me 深度搜索*/
    public int findCircleNum(int[][] isConnected) {
        int res = 0;

        for(int i = 0; i < isConnected.length; i++){
            for(int j = 0; j < isConnected[0].length; j++){

                //每遇到相邻城市，遍历所有相邻,为一个省份
                if(isConnected[i][j] == 1){
                    res++;
                    def(isConnected, i, j);
                }
            }
        }
        return res;
    }

    public void def(int[][] isConnected, int i, int j){
        if(i < 0 || i >= isConnected.length || j < 0 || j >= isConnected[0].length || isConnected[i][j] == 0){
            return;
        }
        //标记
        isConnected[i][j] = 0;
        //相邻是相互的
        isConnected[j][i] = 0;
        for(int k = 0; k < isConnected[0].length; k++){
            def(isConnected, j, k);
        }
    }
    /*官方思路*/
    //1.广度优先搜索
    public int findCircleNum1(int[][] isConnected) {
        int provinces = isConnected.length;
        boolean[] visited = new boolean[provinces];
        int circles = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < provinces; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    for (int k = 0; k < provinces; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) {
                            queue.offer(k);
                        }
                    }
                }
                circles++;
            }
        }
        return circles;
    }

}
